【week3】646. Maximum Length of Pair Chain 解题报告

646. Maximum Length of Pair Chain

题目

You are given n pairs of numbers. In every pair, the first number is always smaller than the second number.

Now, we define a pair (c, d) can follow another pair (a, b) if and only if b < c. Chain of pairs can be formed in this fashion.

Given a set of pairs, find the length longest chain which can be formed. You needn’t use up all the given pairs. You can select pairs in any order.

Example 1:

Input: [[1,2], [2,3], [3,4]]
Output: 2
Explanation: The longest chain is [1,2] -> [3,4]

Note:

1. The number of given pairs will be in the range [1, 1000].

解题报告

题意很简单，若 b < c，则可以将 (a, b) 和 (c, d) 连起来，求能连成的长链最长长度。

可以想到，首先要把传入的 pairs 进行排序方便后续的处理，因为题目用到了 pair[1]，所以以这个为基准从小到大排序。

接链子的最关键之处是每次都选尾尽量小的，而刚开始排序便提供了便利。只要把 pairs 遍历一遍，能接的接上，并记录下链尾的值，再去找下一段就可以找到最长的链子长度。算法的时间复杂度是 $O(nlogn)$，主要是排序花费。

为什么要选尽量小的？

显然，如果大的能接上，那么小的也肯定能接上，而小的能接更多的链子。也因此要选择最小的头作为开始。所以要选尽量小的。

Solution

class Solution {
public:
    int findLongestChain(vector<vector<int>>& pairs) {
        auto cmp = [](const vector<int> &l, const vector<int> &r) { return l[1] < r[1]; };
        sort(pairs.begin(), pairs.end(), cmp);
        int res = 0;
        for (int i = 0, j = 0; i < pairs.size(); ++i) {
            if (i == 0 || pairs[j][1] < pairs[i][0]) {
              ++res;
              j = i;
            }
        }
        return res;
    }
};